interface IHashMap<T> {
    put(key: string, value: T): void
    remove(key: string): [string, T] | undefined
    get(key: string): T | undefined
}

class HashMap<T> implements IHashMap<T> {

    content: [string, T][][] = []
    private length: number = 7
    private prime: number = 31
    private count: number = 0

    constructor() {
        this.content = new Array(this.length)
    }

    // 通过key获取下标
    private hashFn(key: string, max: number): number {
        let hashCode = 0
        const keyLength = key.length
        for (let i = 0; i < keyLength; i++) {
            // 霍纳算法, 计算hashCode的值
            hashCode = this.prime * hashCode + key.charCodeAt(i)
        }
        return hashCode % max
    }

    // 抛出哈希表
    getContent(): [string, T][][] {
        return this.content
    }

    // 查找
    get(key: string): T | undefined {
        const idx = this.hashFn(key, this.length)
        const bucket = this.content[idx] || []
        for (let i = 0; i < bucket.length; i++) {
            const tuple = bucket[i]
            if (tuple[0] === key) {
                return tuple[1]
            }
        }
        return undefined
    }

    // 添加or修改
    put(key: string, value: T) {
        const idx = this.hashFn(key, this.length)
        this.content[idx] = this.content[idx] || []
        const bucket = this.content[idx]

        // 查询是否已经存在
        let isExist = false
        for (let i = 0; i < bucket.length; i++) {
            const tuple = bucket[i]
            if (tuple[0] === key) {
                // 修改
                isExist = true
                tuple[1] = value
            } else {
                // 无操作
            }
        }

        // 没有找到，新增
        if (!isExist) {
            bucket.push([key, value])
            this.count++
            this.resize()

        }


    }

    // 删除
    remove(key: string) {
        const idx = this.hashFn(key, this.length)
        const bucket = this.content[idx] || []
        for (let i = 0; i < bucket.length; i++) {
            const tuple = bucket[i]
            if (tuple[0] === key) {
                bucket.splice(i, 1)
                this.count--
                this.resize()
                return tuple
            }
        }
        return undefined
    }

    // 负载因子 = 元素数量 / 数组长度
    private getLoadFactor(): number {
        return this.count / this.length
    }
    // 判断质数
    private isPrime(num: number) {
        if (num < 2) {
            return false
        }
        for (let i = 2; i < num - 1; i++) {
            if (num % i === 0) {
                return false
            }
        }
        return true
    }

    // 获取周边质数
    private getPrime(num: number) {
        while (!this.isPrime(num)) {
            num++;
        }
        return num < 7 ? 7 : num
    }
    // 扩容和缩容
    private resize() {
        // 判断负载因子
        const loadFactor = this.getLoadFactor()
        console.log('负载因子', loadFactor);

        if (loadFactor > 0.75) {
            // 扩容
            this.length = this.getPrime(this.length * 2)
            console.log('扩容，新的数组长度为', this.length);

            // 重新哈希
            this.rehash()
        }
        if (loadFactor < 0.25 && this.length > 7) {
            // 缩容
            this.length = this.getPrime(this.length / 2)
            this.rehash()
        }
    }

    // 重新哈希
    rehash() {
        console.log('重新整理数据');

        const oldContent = this.content
        const cells = []
        for (let i = 0; i < oldContent.length; i++) {
            if (!oldContent[i]) {
                continue
            }
            for (let j = 0; j < oldContent[i].length; j++) {
                cells.push(oldContent[i][j])
            }
            this.content = new Array(this.length)
        }
        for (let i = 0; i < cells.length; i++) {
            const tuple = cells[i]
            this.put(tuple[0], tuple[1])
        }
    }
}


const hm1 = new HashMap()
hm1.put('a', 1)
hm1.put('b', 5)
hm1.put('c', 1)
hm1.put('d', 1)
hm1.put('e', 1)
hm1.put('f', 1)
// hm1.put('g', 1)
// hm1.put('h', 1)
// hm1.put('i', 1)
// hm1.put('j', 1)
console.dir(hm1.getContent());
// hm1.remove('j')
// console.dir(hm1.getContent());
// console.log('get-a', hm1.get('a'));



// 负载因子 0.14285714285714285
// 负载因子 0.2857142857142857
// 负载因子 0.42857142857142855
// 负载因子 0.5714285714285714
// 负载因子 0.7142857142857143
// 负载因子 0.8571428571428571
// 扩容，新的数组长度为 17
// 重新整理数据
// 负载因子 0.4117647058823529
// 负载因子 0.47058823529411764
// 负载因子 0.5294117647058824
// 负载因子 0.5882352941176471
// 负载因子 0.6470588235294118
// 负载因子 0.7058823529411765
// [
//   [ [ 'f', 1 ] ],
//   <11 empty items>,
//   [ [ 'a', 1 ] ],
//   [ [ 'b', 5 ] ],
//   [ [ 'c', 1 ] ],
//   [ [ 'd', 1 ] ],
//   [ [ 'e', 1 ] ]
// ]